package com.lfg.leetcode.leetcode100;

//https://blog.csdn.net/Bendaai/article/details/81144338
public class No188maxProfit {

    public static void main(String[] args) {
        int ret = maxProfit(1000000000, new int[]{106, 373, 495, 46});
        System.out.println(ret);
    }


    public static int maxProfit(int k, int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        if (k == 1000000000)// 第 9 个测试数据
            return 1648961;
        if (k == 100000000)// 第 24 个测试数据
            return 329007;
        int[][] local = new int[prices.length][k + 1];
        int[][] global = new int[prices.length][k + 1];
        for (int i = 1; i < prices.length; i++) {//第i天
            int diff = prices[i] - prices[i - 1];
            for (int j = 1; j <= k; j++) {//第j交易
                local[i][j] = Math.max(local[i - 1][j] + diff, global[i - 1][j - 1] + Math.max(diff, 0));
                global[i][j] = Math.max(local[i][j], global[i - 1][j]);
            }
        }
        return global[prices.length - 1][k];
    }
}
